/* =============================================================================
 * PROJET           	: repartition
 * NOM DU FICHIER   	: optimisation.c
 * OBJET            	: Definition des fonctions d'optimisation de la solution
 * ------------------------------------------------------------------------------
 * DATE DE CREATION 	: 27/10/2009
 * AUTEUR           	: Sha LIU, Yves BOGE
 * ============================================================================= */

#include "optimisation.h"


/* description :	procedure de calcul des f(x)
 * entree :			element de type t_donne_pb
 * sortie :			pb avec les f(x), fmoins, et fplus calcules
 */
void calc_f(t_donnees_pb* pb)
{
	int i;

	for ( i = 0 ; i < pb->nb_pop ; i++ ) {
		(pb->dep + i)->fx = - (float)(pb->dep + i)->rep / (pb->dep + i)->pop;
		(pb->dep + i)->fmoins = - (float)((pb->dep + i)->rep - 1) / (pb->dep + i)->pop;
		(pb->dep + i)->fplus = - (float)((pb->dep + i)->rep + 1) / (pb->dep + i)->pop;
		
		//printf("departement %i : rep = %i, pop = %i, f(x) = %f, f(x-1) = %f, f(x+1) = %f\n",
		 //i+1, (pb->dep + i)->rep, (pb->dep + i)->pop, (pb->dep + i)->fx, (pb->dep + i)->fmoins, (pb->dep + i)->fplus);
	}
}




/* description :	procedure de determination de r, s, k, l
 * entree :			element de type t_donne_pb
 * sortie :			tableau contenant les indice de r, s, k, l
 */
int* get_rskl(t_donnees_pb* pb){
	int *indice = (int*)malloc(4*sizeof(int)); 
	int i;
	float fxgrand = (pb->dep)->fx;
	float fxpetit = (pb->dep)->fx;
	float fmoinspetit = (pb->dep)->fmoins;
	float fplusgrand = (pb->dep)->fplus;
	indice[0] = 0;
	indice[1] = 0;
	indice[2] = 0;
	indice[3] = 0;

	// pb->dep est le premier departement, 
	for ( i = 1 ; i < pb->nb_pop; i++ ) {
		// determiner r
		if( fxgrand < (pb->dep + i)->fx ){
			fxgrand = (pb->dep + i)->fx;
			indice[0] = i;
		}

		// determiner s		
		if( fxpetit > (pb->dep + i)->fx){
			fxpetit = (pb->dep + i)->fx;
			indice[1] = i;
		}
		
		// determinier k
		if( (fmoinspetit > (pb->dep + i)->fmoins  ) ) {
			fmoinspetit = (pb->dep + i)->fmoins;
			indice[2] = i;
		}
		
		// determinier l
		if( (fplusgrand < (pb->dep + i)->fplus  ) ) {
			fplusgrand = (pb->dep + i)->fplus;
			indice[3] = i;
		}
	}
	
	return indice;
}





/* description :	partie principale de la resolution
 * entree :			element de type t_donne_pb
 * sortie :			trace et fichier contenant la solution
 */
t_donnees_pb* resolution(t_donnees_pb* pb, bool trace_on){
	int *ind; 
	int r, s, k, l;
	
	calc_f(pb);
	
	ind = get_rskl(pb);
	r = ind[0];
	s = ind[1];
	k = ind[2];
	l = ind[3];
	
	//printf("Partie 1\n");
	
	if (trace_on) {
		ecrire("1: "); trace(0, pb); ecrire("\n");
	}
	
	//printf("r = %i, s = %i, k = %i, l = %i\n", r, s, k, l);
	// X est optimal, on ecrit la solution dans le fichier
	if( (pb->dep + r)->fx <=  (pb->dep + k)->fmoins && (pb->dep + l)->fplus <= (pb->dep + s)->fx ) {
		if (trace_on) {
			trace(1, pb); ecrire("*\n");
		}
	}
		
	// X appartient a A
	else if( (pb->dep + r)->fx <=  (pb->dep + k)->fmoins && (pb->dep + l)->fplus > (pb->dep + s)->fx ) {
		pb = algo_part_5(pb, trace_on);
	}
		
	// X appartient a B
	else if( (pb->dep + r)->fx >  (pb->dep + k)->fmoins && (pb->dep + l)->fplus <= (pb->dep + s)->fx ) {
		pb = algo_part_4(pb, trace_on);
	}
		
	// passer a part 2
	else {
		pb = algo_part_2(pb, trace_on);
	}
	
	return pb;
}




/* description :	deuxieme partie de l'algorithme
 * entree :			element de type t_donne_pb
 * sortie :			redirection vers une autre partie de l'algorithme
 */
t_donnees_pb* algo_part_2(t_donnees_pb* pb, bool trace_on){
	int *ind;  
	int r, s, k, l;
	
	ind = get_rskl(pb);
	r = ind[0];
	s = ind[1];
	k = ind[2];
	l = ind[3];
	
	if (trace_on) {
		ecrire("2: "); trace(0, pb); ecrire("\n");
	}
	//printf("Partie 2\n");
	
	// appeler part 3
	if( (pb->dep + r)->fx <= (pb->dep + s)->fmoins && (pb->dep + r)->fplus <= (pb->dep + s)->fx )
		pb = algo_part_3(pb, trace_on);
		
	// set Xs <- Xs-1, Xr <- Xr+1, puis redeterminer les indices r, s, k, l
	else if( (pb->dep + r)->fx > (pb->dep + s)->fmoins && (pb->dep + r)->fplus > (pb->dep + s)->fx ){
		(pb->dep + s)->rep = (pb->dep + s)->rep - 1;
		(pb->dep + r)->rep = (pb->dep + r)->rep + 1;
		pb = resolution(pb, trace_on);	
	}
	
	// set Xs <- Xs-1, Xl <- Xl+1, puis redeterminer les indices r, s, k, l 
	else if( (pb->dep + r)->fx > (pb->dep + s)->fmoins && (pb->dep + r)->fplus <= (pb->dep + s)->fx ){
		(pb->dep + s)->rep = (pb->dep + s)->rep - 1;
		(pb->dep + l)->rep = (pb->dep + l)->rep + 1;
		pb = resolution(pb, trace_on);			
	}
	
	// set Xk <- Xk-1, Xr <- Xr+1, puis redeterminer les indices r, s, k, l 
	else{
		(pb->dep + k)->rep = (pb->dep + k)->rep - 1;
		(pb->dep + r)->rep = (pb->dep + r)->rep + 1;
		pb = resolution(pb, trace_on);				
	}
	
	return pb;
}




/* description :	troisieme partie de l'algorithme
 * entree :			element de type t_donne_pb
 * sortie :			donnees du probleme modifie
 */
t_donnees_pb* algo_part_3(t_donnees_pb* pb, bool trace_on)
{	
	int *ind; 
	int r, s, k, l;
	int i;
	
	ind = get_rskl(pb);
	r = ind[0];
	s = ind[1];
	k = ind[2];
	l = ind[3];

	//printf("Partie 3\n");
	if (trace_on) {
		ecrire("3: "); trace(0, pb); ecrire("\n");
	}
	
	// trouver les valeurs de k et l jusqu'au X appartient a C
	while( (pb->dep + l)->fplus > (pb->dep + k)->fmoins ){
		(pb->dep + k)->rep = (pb->dep + k)->rep - 1;	
		(pb->dep + l)->rep = (pb->dep + l)->rep + 1;
		for ( i = 0 ; i < pb->nb_pop ; i++ ) {
			// determiner k
			if( (pb->dep + i)->fmoins <= (pb->dep + i + 1)->fmoins  ){
				k = i;
			}
			else{	
				k = i + 1;
			}
			
			// determinier l
			if( (pb->dep + i)->fplus <= (pb->dep + i + 1)->fplus  ){
				l = i + 1;
			}
			else{	
				l = i;
			}		
		}
	}
	
	// une fois x appartient a C, appeler part 4
	pb = algo_part_4(pb, trace_on);
	
	return pb;
}




/* description :	quatrieme partie de l'algorithme
 * entree :			element de type t_donne_pb
 * sortie :			redirection vers une autre partie de l'algorithme ou fin
 */
t_donnees_pb* algo_part_4(t_donnees_pb* pb, bool trace_on) {

	
	int* rskl;				//	tableau contenant r, s, k et l
	int t_cour, i, j;		// variables compteur
	float fxz = 0;			// valeur du fi(xi - zi) courant
	float max_fxz;			// maximum des fi(xi - zi)
	float min_max;			// minimum des maximums
	int q;					// cardinal de Jt>
	int* z_opti = NULL;		// z optimal
	t_donnees_pb* copie_pb;	// copie temporaire du pb
	

	void arrangements_z(int n, int p, int k, int *L, int som) {
		int i, j;
		
		
		// Si l'on est sur un arrangement : cas de base
		if(k==p) {
		
			// on test tous les i de Jt<= pour chercher le max de fi(xi - zi)
			max_fxz = -10;
			j = 0;
			for ( i = 0 ; i < pb->nb_pop ; i++ ) {
				if ( (pb->dep + i)->fx <= (pb->dep + t_cour)->fx ) {
					// un z pour une population
					fxz = ( -(float)( (pb->dep + i)->rep - L[j] ) / (pb->dep + i)->pop );
					//printf("f(%i - %i) = %f\n", (pb->dep + i)->rep, L[j], fxz);
					
					// on regarde si le f(xi - zi) est le nouveau max
					if ( fxz > max_fxz )
						max_fxz = fxz;
					j++;
				}
			}
			
			// Si le max calcule est le nouveau min
			if ( max_fxz < min_max ) {
				min_max = max_fxz;
				// on sauvegarde le z :
				for( j = 0 ; j < p ; j++ )
					z_opti[j] = L[j];
			}
		}
		// cas recursif final :
		else if (k == (p - 1)) {
			L[k] = n - som;
			arrangements_z(n, p, k+1, L, n);
		}
		// cas recursif normal :
		else {
		
			for( i = 0 ; i <= (n - som) ; i++ ) {
				L[k] = i;
				arrangements_z(n, p, k+1, L, som + i);
			}
		}

	}
	
	// -------------pour test-------------------
	//calc_f(pb);
	// -------------pour test-------------------
	
	rskl = get_rskl(pb);
	
	
	//printf("Partie 4\n");
	if (trace_on) {
		ecrire("4: "); trace(0, pb); ecrire("\n");
	}
	
	// On parcours les populations
	bool opti = true;
	for ( t_cour = 0 ; t_cour < pb->nb_pop ; t_cour++ ) {
		
		// Si la population courante n'est pas dans R
		// on cherche le min de tous les max
		if ( (pb->dep + t_cour)->fx != (pb->dep + rskl[0])->fx ) {
			
			//printf("pour t = %i\n", t_cour);
			
			// calcul de q :
			q = 0;
			for ( i = 0 ; i < pb->nb_pop ; i++ ) {
				//printf("\tf(xi) = %f, f(xt) = %f\n", (pb->dep + i)->fx, (pb->dep + t_cour)->fx);
				if ( (pb->dep + i)->fx > (pb->dep + t_cour)->fx )
					q++;
			}
			
			// si q est différent de 0
			if ( q != 0 ) {
			
				// allocation memoire pour z_opti
				z_opti = malloc( sizeof(int) * (pb->nb_pop - q) );
			
				//printf("arrangements de %i parmis %i :\n", pb->nb_pop - q, q);
			
				// calcule du z optimal par une fonction de recherche des
				// arrangements.
				min_max = 10;
				int L[pb->nb_pop - q];
				arrangements_z(q, pb->nb_pop - q, 0, L, 0);
			
				// affichage de z_opti :
				/*printf("z optimal : (%i", z_opti[0]);
				for ( i = 1 ; i < (pb->nb_pop - q) ; i++ )
					printf(", %i", z_opti[i]);
				printf(")\n");*/
		
				// on fait une sauvegarde de la structure
				copie_pb = copier_probleme(pb);
		
				// On parcours les populations
				j = 0;
				for ( i = 0 ; i < pb->nb_pop ; i++ ) {
					// si i appartient a Jt>
					if ( (copie_pb->dep + i)->fx > (pb->dep + t_cour)->fx )
						(copie_pb->dep + i)->rep++;
				
					// si i appartient a Jt<=
					else {
						(copie_pb->dep + i)->rep -= z_opti[j];
						j++;
					}
				}
				
				// On calcul les f(x), r et s pour le nouveau pb
				int* nouv_rskl;
				calc_f(copie_pb);
				nouv_rskl = get_rskl(copie_pb);
				
				// On reparcours les populations pour regarder si la solution est optimal
				for ( i = 0 ; i < copie_pb->nb_pop ; i++ ) {
					// si la population n'est pas dans R
					if ( (copie_pb->dep + t_cour)->fx != (copie_pb->dep + rskl[0])->fx ) {
						// on teste si l'optimalite est fausse
						if ( ( (pb->dep + rskl[0])->fx - (pb->dep + rskl[1])->fx ) > ( (copie_pb->dep + nouv_rskl[0])->fx - (copie_pb->dep + nouv_rskl[1])->fx ) )
							opti = false;
					}
				}
				
			}
			
		}
		
	}
				
	// Si la solution est optimal, on arrete
	if ( opti ) {
		if (trace_on) {
			trace(1, pb); ecrire("*\n");
		}
		
		// Si x appartient a C, on recherche une autre solution avec la partie 5
		if ( (	pb->dep + rskl[0])->fplus 		< (pb->dep + rskl[1])->fx
				&& (pb->dep + rskl[1])->fx 		< (pb->dep + rskl[3])->fplus
				&& (pb->dep + rskl[3])->fplus	< (pb->dep + rskl[2])->fmoins
				&& (pb->dep + rskl[2])->fmoins	< (pb->dep + rskl[0])->fx
				&& (pb->dep + rskl[0])->fx		< (pb->dep + rskl[1])->fmoins ) {
			
			if (trace_on) {
				trace(1, pb); ecrire("(5)\n");
			}
			copie_pb = copier_probleme(pb);
			pb->sol_suiv = (struct t_donnees_pb*) algo_part_5(copie_pb, trace_on);
			t_donnees_pb* temp = (t_donnees_pb*) pb->sol_suiv;
			pb->nb_sol = temp->nb_sol + 1;
		}
				
	}
	else {
		// on met a jour les donnees du probleme puis on lance la partie 1
		pb = copier_probleme(copie_pb);
		if (trace_on) {
			trace(1, pb); ecrire("(1)\n");
		}
		pb = resolution(pb, trace_on);
	}
	
	return pb;
}



/* description :	cinpuieme partie de l'algorithme
 * entree :			element de type t_donne_pb
 * sortie :			redirection vers une autre partie de l'algorithme ou fin
 */
t_donnees_pb* algo_part_5(t_donnees_pb* pb, bool trace_on) {

	
	int* rskl;				//	tableau contenant r, s, k et l
	int t_cour, i, j;		// variables compteur
	float fxy = 0;			// valeur du fj(xj + yj) courant
	float min_fxy;			// minimum des fj(xj + yj)
	float max_min;	// maximums des minimums 
	int p;					// cardinal de Jt<
	int* y_opti = NULL;		// y optimal
	t_donnees_pb* copie_pb;	// copie temporaire du pb
	

	void arrangements_y(int n, int q, int k, int *L, int som) {
		int i, j;
		
		
		// Si l'on est sur un arrangement : cas de base
		if(k==q) {
		
			//printf("arrangement courant : ("); for (i = 0 ; i < q ; i++) printf("%i ", L[i]); printf(")\n");
			// on test tous les j de Jt>= pour chercher le min de fj(xj + yj)
			min_fxy = 10;
			i = 0;
			for ( j = 0 ; j < pb->nb_pop ; j++ ) {
				if ( (pb->dep + j)->fx >= (pb->dep + t_cour)->fx ) {
					// un y pour une population
					fxy = ( -(float)( (pb->dep + j)->rep + L[i] ) / (pb->dep + j)->pop );
					//printf("f(%i + %i) = %f\n", (pb->dep + j)->rep, L[i], fxy);
					
					// on regarde si le fj(xj + yj) est le nouveau min
					if ( fxy < min_fxy )
						min_fxy = fxy;
					i++;
				}
			}
			
			// Si le min calcule est le nouveau max
			if ( min_fxy > max_min ) {
				max_min = min_fxy;
				// on sauvegarde le y :
				//printf("nouvel optimum\n");
				for( i = 0 ; i < q ; i++ )
					y_opti[i] = L[i];
			}
		}
		// cas recursif final :
		else if (k == (q - 1)) {
			L[k] = n - som;
			arrangements_y(n, q, k+1, L, n);
		}
		// cas recursif normal :
		else {
		
			for( j = 0 ; j <= (n - som) ; j++ ) {
				L[k] = j;
				arrangements_y(n, q, k+1, L, som + j);
			}
		}

	}
	
	rskl = get_rskl(pb);
	
	
	//printf("Partie 5\n");
	if (trace_on) {
		ecrire("5: "); trace(0, pb); ecrire("\n");
	}
	
	// On parcours les populations
	bool opti = true;
	for ( t_cour = 0 ; t_cour < pb->nb_pop ; t_cour++ ) {
		
		// Si la population courante n'est pas dans S
		// on cherche le max de tous les mins
		if ( (pb->dep + t_cour)->fx != (pb->dep + rskl[1])->fx ) {
			
			//printf("pour t = %i\n", t_cour);
			
			// calcul de p :
			p = 0;
			for ( i = 0 ; i < pb->nb_pop ; i++ ) {
				//printf("\tf(xi) = %f, f(xt) = %f\n", (pb->dep + i)->fx, (pb->dep + t_cour)->fx);
				if ( (pb->dep + i)->fx < (pb->dep + t_cour)->fx )
					p++;
			}
			
			// si p est différent de 0
			if ( p != 0 ) {
			
				// allocation memoire pour y_opti
				y_opti = malloc( sizeof(int) * (pb->nb_pop - p) );
			
				//printf("arrangements de %i parmis %i :\n", pb->nb_pop - p, p);
			
				// calcule du y optimal par une fonction de recherche des
				// arrangements.
				max_min = -10;
				int L[pb->nb_pop - p];
				arrangements_y(p, pb->nb_pop - p, 0, L, 0);
			
				// affichage de y_opti :
				/*printf("y optimal : (%i", y_opti[0]);
				for ( j = 1 ; j < (pb->nb_pop - p) ; j++ )
					printf(", %i", y_opti[j]);
				printf(")\n");*/
		
				// on fait une sauvegarde de la structure
				copie_pb = copier_probleme(pb);
		
				// On parcours les populations
				i = 0;
				for ( j = 0 ; j < pb->nb_pop ; j++ ) {
					// si j appartient a Jt<
					if ( (copie_pb->dep + j)->fx < (pb->dep + t_cour)->fx )
						(copie_pb->dep + j)->rep--;
				
					// si j appartient a Jt>=
					else {
						(copie_pb->dep + j)->rep += y_opti[i];
						i++;
					}
				}
				
				// On calcul les f(x), r et s pour le nouveau pb
				int* nouv_rskl;
				calc_f(copie_pb);
				nouv_rskl = get_rskl(copie_pb);
				
				// On reparcours les populations pour regarder si la solution est optimal
				for ( j = 0 ; j < copie_pb->nb_pop ; j++ ) {
					// si la population n'est pas dans S
					if ( (copie_pb->dep + t_cour)->fx != (copie_pb->dep + rskl[1])->fx ) {
						// on teste si l'optimalite est fausse
						if ( ( (pb->dep + rskl[0])->fx - (pb->dep + rskl[1])->fx ) > ( (copie_pb->dep + nouv_rskl[0])->fx - (copie_pb->dep + nouv_rskl[1])->fx ) )
							opti = false;
					}
				}
				
			}
			
		}
		
	}
				
	// Si la solution est optimal, on arrete
	if ( opti ) {
		if (trace_on) {
			trace(1, pb); ecrire("*\n");
		}
	}
	
	else {
		// on met a jour les donnees du probleme puis on lance la partie 1
		pb = copier_probleme(copie_pb);
		if (trace_on) {
			trace(1, pb); ecrire("(1)\n");
		}
		pb = resolution(pb, trace_on);
	}
	
	return pb;
}
